#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "haf.h"
#include <pthread.h>
void swap(struct haftree *p,struct haftree *q){
	struct haftree swap;
	swap = *p;
	*p = *q;
	*q = swap;
}

struct haftree dui(struct haftree *phf,int len){
	int i,j;
	struct haftree l,r,c,*pl,*pr,*pc; 
	if(len%2!=0){
		i = len/2;
	}else{
		i = len/2-1;
	}
	for(i;i>=0;--i){
		j = i;
		while(2*j+1 < len){
			struct haftree *phftree = NULL;
			int ladd = 2*j+1, radd =0;
			c = phf[j];
			l = phf[ladd];
			if((c.v > l.v) || (2*j+2 < len && c.v > phf[2*j+2].v)){
				pc = &phf[j];
				pl = &phf[ladd];
				phftree = &phf[ladd];
				if(2*j+2 < len){
					radd = 2*j+2;
					r = phf[radd];
					pr = &phf[radd];
					phftree = (struct haftree *)MAX(pl,pr);
				}
				swap(phftree,pc);
			}
			if(l.v != phf[ladd].v){
				j = 2*j+1;	
			}else if((2*j+2 < len) && (r.v != phf[radd].v)){
				j = 2*j+2;
			}else{
				break;
			}
		}
	}
	swap(phf,phf+len-1);	
	return phf[len-1];
}

void mkcode(struct haftree *p,char *pcode){
	p->code = pcode;
	if(!p->l && !p->r){
		if(strlen(pcode)==0){
			pcode = (char *)malloc(2);
			strcat(pcode,"0");
			p->code = pcode;
		}
		code[p->dq] = pcode;
		++code_sum;
	}
	if(p->l){
		char *str = (char *)malloc(strlen(pcode)+2);
		strcpy(str,pcode);
		mkcode(p->l,strcat(str , "0"));
	}
	if(p->r){	
		char *str = (char *)malloc(strlen(pcode)+2);
		strcpy(str,pcode);
		mkcode(p->r,strcat(str , "1"));
	}
}

void bianlifree(struct haftree *p,struct haftree *q){
	if(p){
		bianlifree(p->l,q);
		bianlifree(p->r,q);
		if(p!=q){
			free(p);
		}
	}
}

void hafcode(struct haftree *p,int len){
	int j = len;
	while(dui(p,j).v == 0){
		--j;
	}
	for(int i=j-1;i>0;--i){
		struct haftree *a1,*a2,*pa;
		a1 = (struct haftree *)malloc(sizeof(struct haftree));
		a2 = (struct haftree *)malloc(sizeof(struct haftree));
		pa = (struct haftree *)malloc(sizeof(struct haftree));
		*a1 = dui(p,i+1);
		*a2 = dui(p,i);
		pa->v = a1->v + a2->v;
		pa->l = a1;
		pa->r = a2;
		p[i-1] = *pa;
		free(pa);
		}
	mkcode(p,"");
	bianlifree(p,p);
}

void hafdu(unsigned char* buf,int b,long weizhi,FILE *ofg){
	unsigned char h,l;
	if(pthread_mutex_lock(&mutex)!=0){
		perror("互斥锁出问题");
		exit(1);
	}

	for(int i=0;i<b;++i){
		LIDU_8(buf,arr,i);
	}
	if(pthread_mutex_unlock(&mutex)!=0){
		perror("互斥锁出问题");
		exit(1);
	}

}

sy hafout(sy y,unsigned char* buf,int b,long weizhi,FILE *ofg){
	unsigned zijie = 0,wei;
	char *a;
	sy s;
	int jilu = 0,i=0,o=0,ilidu=0,le=0;
	unsigned char *out = (unsigned char *)malloc(b);
	if(y.yshyu != 0){
		zijie = y.shyu;
		jilu = y.yshyu;
	}
out:
	for(i;i<b;++i){
		ilidu = 0;
		for(ilidu;ilidu<8;++ilidu){
			a = code[buf[i]];
			le = strlen(a);
			while(1){
				wei = 0x01;
				for(int j=jilu;j<8;++j){
					if(*a == '1'){
						wei = 0x01 << j;
						zijie|=wei;
					}else if(*a=='\0'){
						jilu = j;
						++i;
						goto out;
					}
					++a;
					++jilu;
				}
				jilu = 0;
				out[o] = zijie;
				++o;
				zijie = 0;
				if(o>=b){
					out = (unsigned char *)realloc(out,b*2);
				}
			}
		}
	}
	if(b!=0){
		if(fwrite(out,o,1,ofg)!=1){
			free(out);
			perror("文件输出错误");
			exit(1);
		}
		if(jilu != 0){
			s.yshyu = jilu;
			s.shyu = zijie;
			if(weizhi<=0){
				unsigned char wei1[2];
				wei1[0] = s.shyu;
				wei1[1] = s.yshyu;
				if(fwrite(wei1,2,1,ofg)!=1){
					free(out);
					perror("文件写入错误");
					exit(1);
				}
			}
		}else{
			s.yshyu = 0;
			s.shyu = 0;
			if(weizhi<=0){
				unsigned char wei2;
				wei2 = 8;
				if(fwrite(&wei2,1,1,ofg)!=1){
					free(out);
					perror("文件写入错误");
					exit(1);
				}
			}

		}
		fflush(ofg);
	}
	free(out);
	return s;
}

void filepinjie(unsigned char* buf,int b,long weizhi,FILE *ofg){
	
	if(b!=0 && fwrite(buf,b,1,in)!=1){
		perror("文件写入错误");
		exit(1);
	}

}

void xietou(FILE *ff){
	char *p = (char*)malloc(6);
	char *q = p;
	int jishu = 0,len = 6;
	p[0] = code_sum-1;
	p[1] = 0;
	int *pi = (int *)(p+2);
	long *lp,weizhilen=0;
	*pi = namelen;
	for(unsigned int i=0;i<256;++i){
		if(code[i]){
			jishu = len;
			len = len + strlen(code[i])+2;
			p = (char*)realloc(p,len);
			q = p+jishu;
			*q = i;
			++q;
			for(int j = 0;j<=strlen(code[i]);++j){
				*q = *(code[i]+j);
				++q;
			}

		}
	}
	weizhilen = len + (sizeof(bao)-sizeof(p)*3)*(namelen);
	for(int j=0;j<namelen;++j){
		weizhilen = weizhilen + (strlen(fgs[j].name)+1);
	}
	for(int i=0;i<namelen;++i){
		jishu = len;
		len = len + strlen(fgs[i].name)+17;
		p = (char*)realloc(p,len);
		q = p + jishu;
		*q = strlen(fgs[i].name);
		++q;
		for(int j=0;j<strlen(fgs[i].name);++j){
			*q = *(fgs[i].name+j);
			++q;
		}
		lp = (long*)q;
		*lp = weizhilen;
		q+=8;
		lp = (long*)q;
		*lp = fgs[i].len;
		weizhilen+= fgs[i].len;
	}
	if(p && fwrite(p,len,1,ff)!=1){
		perror("文件写入错误");
		exit(1);
	}
	free(p);
}

int xy(int x,int y){
	int a = 1;
	for(int i=0;i<y;++i){
		a=x*a;
	}
	return a;
}

int equlcode(long_code *la,unsigned long long *lb,int len){
	int v = 1;
	if(la->len == len){
		for(int i=0;i<len;++i){
			if((la->du)[i] != lb[i]){
				v = 0;
				break;
			}
		}
	}else{
		v=0;
	}
	return v;

}

sy hafin(sy y,unsigned char* buf,int b,long weizhi,FILE *ofg){
	unsigned long long du=0,wei;
	unsigned char a,awei;
	sy s;
	int jishu = 0,lln,i=0,o=0,ilidu=0,wai,zichang=64;
	unsigned char *out = (unsigned char *)malloc(8192);
	unsigned long long *lp= (unsigned long long*)malloc(sizeof(unsigned long long));
	if(y.yshyu != 0){
		du = y.lshyu;
		jishu = y.yshyu;
	}
	while(1){
		zichang = 64;
		wei = 0x0000000000000001;
		lln = 8;
		for(wai=0;wai<1;++wai){
			ilidu = 0;
			awei = 0x01;
			if(i>b-1){
				goto out;
			}
			a = buf[i];
			if((weizhi<=0) && (i==b-2 || b-2<0)){
				lln = buf[b-1];
			}
			for(ilidu;ilidu<lln;++ilidu){
			
				if(a & awei){
					wei = 0x0000000000000001<<(jishu%64);
					du = du | wei;	
				}
				awei = awei<<1;
				++jishu;
				if(jishu>zichang){
					lp = (unsigned long long*)realloc(lp,(jishu/64)+1);
					lp[jishu/64] = du;
					zichang+=64;
					du = 0;
				}
				if(jishu>0 && jishu<11){
					if((code_tab[jishu])){
						if((code_tab[jishu])[du]){
							out[o] = *(code_tab[jishu])[du];
							jishu = 0;
							du = 0;
							++o;
						}
					}
				}else if(jishu>=11 && jishu <256){
					unsigned long long du1 = du;
					if((lcode_tab[jishu])){
						du = du >> (jishu/8)*8;
						if(((lcode_tab[jishu])[du])){
							long_code *p = (lcode_tab[jishu])[du];
							int len = (jishu/65)+1;
							while(p){
								if(equlcode(p,&du1,len)>0){
									out[o] = p->val;
									du1 = 0;
									jishu = 0;
									++o;
									break;
								}else{
									p = p->next;
								}
							}
						}
							du = du1;
					}
				}
				if(o>8191){
					out = (unsigned char*)realloc(out,o*2);
				}
			}
			++i;
			if(i>=b-1 && (weizhi<=0)){
				goto out;
			}

		}
	}
out:
	if(b>1){
		if(jishu!=0){
			s.lshyu = du;
			s.yshyu = jishu;
		}else{
			s.yshyu = 0;
			s.lshyu = 0;
		}

		if(fwrite(out,o,1,ofg)!=1){
			free(out);
			free(lp);
			perror("文件写入错误");
			exit(1);
		}
		fflush(ofg);
	}
	free(lp);
	free(out);
	return s;
}

void in_open(FILE *ff){
	int tou_size,*flen;
	unsigned char **c,*cv;
	long_code **lc = NULL;
	unsigned char tou[6];
	unsigned char bt = 1,val;
	int jishu=0,zichang = 64;
	unsigned long long du = 0,duyu = 1,*lp;
	long lnn[2];
	if(fread(tou,6,1,ff) != 1){
		perror("文件读取错误");
		exit(1);
	}
	flen = (int *)(tou+2);
	namelen = *flen;
	for(int i=0;i<(tou[0]+1);++i){
		bt = 1;
		jishu = 0;
		val = 0;
		du = 0;
		zichang = 64;
		lp= (unsigned long long*)malloc(sizeof(unsigned long long));
		if(fread(&val,1,1,ff) != 1){
			perror("文件读取错误");
			exit(1);
		}
		while(bt!=0x00){
			if((fread(&bt,1,1,ff)) != 1){
				perror("文件读取错误");
				exit(1);
			}
			if(bt == 0x31){
				du = du | (duyu << (jishu % 64));
				if(jishu>zichang){
					*lp = du;
					lp = (unsigned long long*)realloc(lp,sizeof(unsigned long long)*((jishu/64)+1));
					zichang+=64;
					du = 0;
				}
			}
			if(bt!=0x00){
				++jishu;
			}
		}
		if(jishu>=11){
			lp[(zichang/64)-1] = du;
		}
		if(!code_tab[jishu]&&jishu<=10){
			c = (unsigned char**)calloc(xy(2,jishu),sizeof(*c));
			free(lp);
			code_tab[jishu] = c;
		}else if(!lcode_tab[jishu]&&jishu>10){
			lc = (long_code **)calloc(256,sizeof(*c));
			lcode_tab[jishu] = lc;
		}
		if(jishu<11&&jishu > 0){
			cv = (unsigned char *)malloc(1);
			*cv = val;
			(code_tab[jishu])[du] = cv;
					}else if(jishu>10){
			du = du >> (jishu/8)*8;
			long_code lcode = {zichang/64,val,lp,NULL};
			long_code *plocde = (long_code*)malloc(sizeof(long_code));
			long_code **p = &((lcode_tab[jishu])[du]);
			long_code *llp = *p;
			*plocde = lcode;
			if(llp){	
				while(llp->next){
					llp = llp->next;
				}
				llp->next = plocde;
			}else{
				(lcode_tab[jishu])[du] = plocde;
			
			}
		}

	}	
	fgs = (bao*)malloc(sizeof(bao)*tou[2]);
	for(int k=0;k<*flen;++k){

		if(fread(&val,1,1,ff) != 1){
			perror("文件读取错误");
			exit(1);
		}
		char *lcc = (char*)malloc(val+1);
		char *cp = lcc;
		for(int m=0;m<val;++m){
			if(fread(cp,1,1,ff) != 1){
				perror("文件读取错误");
				exit(1);
			}
			++cp;
		}
		*cp = '\0';
		if(fread(lnn,16,1,ff) != 1){
			perror("文件读取错误");
			exit(1);
		}

		if(inname){
			if((fgs[k].fg = fopen(inname,"rb"))==NULL){
				printf("%s ",inname);
				perror("打开文件错误");
				exit(1);
			}
			fseek(fgs[k].fg,lnn[0],SEEK_SET);
			if((fgs[k].ofg = fopen(lcc,"wb"))==NULL){
				printf("%s ",lcc);
				perror("打开文件错误");
				exit(1);
			}
		}
		fgs[k].name = lcc;
		fgs[k].start = lnn[0];
		fgs[k].len = lnn[1];
	}

	
}

FILE *out_open(char *str){
	FILE *fg;
	if((fg = fopen(str,"wb"))==NULL){
		perror("打开文件错误");
		exit(1);
	}
	return fg;
}
